package leetcode.code0279;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public int numSquares(int n) {
		return this.f(n, (int) Math.sqrt(n), 0);
	}

	private int f(int n, int max, int ans) {
		if (n == 0) {
			return ans;
		}
		if (n < 0 || max == 0) {
			return -1;
		}
		int ans1 = this.f(n, max - 1, ans);
		int ans2 = this.f(n - max * max, (int) Math.sqrt(n - max * max), ans + 1);
		if (ans1 == -1 && ans2 != -1) {
			return ans2;
		} else if (ans2 == -1 && ans1 != -1) {
			return ans1;
		} else {
			return Math.min(ans1, ans2);
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(3, this.numSquares(12));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(2, this.numSquares(13));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug1();
		so.debug2();
//		so.debug3();
//		so.debug4();

	}

}
